package com.duoduo.深度广度优先;

import com.duoduo.TreeNode;

/**
 * @program: algorithm
 * @description: 二叉树的最小深度111
 * @author: chaidl  ！
 * @create: 2022-03-02 11:03
 */
public class 二叉树的最小深度 {
    public static void main(String[] args) {
        TreeNode A = new TreeNode(3);
        TreeNode c = new TreeNode(9);
        TreeNode v = new TreeNode(20);
        TreeNode l = new TreeNode(15);
        TreeNode j = new TreeNode(7);
        A.left = c;
        A.right = v;
        v.left=l;
        v.right=j;
        System.out.println(minDepth2(A));
    }
    public int minDepth3(TreeNode root) {
        if(root == null) return 0;
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        //1.如果左孩子和右孩子有为空的情况，直接返回m1+m2+1
        //2.如果都不为空，返回较小深度+1
        return root.left == null || root.right == null ? m1 + m2 + 1 : Math.min(m1,m2) + 1;
    }
    public static int minDepth2(TreeNode root) {
        if(root ==null){
            return 0;
        }
        int leftDepth=minDepth(root.left);
        int rightDepth=minDepth(root.right);
        // 左指针为空，右深度加一
        if(root.left==null){
            return rightDepth+1;
        }
        // 右指针为空，左加一
        if(root.right==null){
            return leftDepth+1;
        }
        // 左右都不为空，取最小值+1
        return Math.min(leftDepth,rightDepth)+1;
    }
    public static int minDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(root.left==null && root.right==null){
            return 1;
        }
        int min_depth=Integer.MAX_VALUE;
        // 如果左子树不为空就一直向下寻找
        if(root.left!=null){
            min_depth= Math.min(minDepth(root.left),min_depth);
        }
        if(root.right!=null){
            min_depth= Math.min(minDepth(root.right),min_depth);
        }
        return min_depth+1;
    }
}
